package 字符串;

import sun.reflect.generics.tree.Tree;

import javax.swing.tree.TreeNode;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * @Author Weton Li
 * @Date 2021/4/7 10:05
 */
public class 根据二叉树创建字符串 {

    public String method(TreeNode top) {

        Stack<TreeNode> stack = new Stack<>();
        HashSet<TreeNode> visitedSet = new HashSet<>();
        StringBuilder sb = new StringBuilder();

        stack.push(top);

        while (!stack.isEmpty()) {
            top = stack.peek();
            if (!visitedSet.contains(top)) { // 底层调用ContainsKey(top),查询是否有top对应的值
                visitedSet.add(top);
                sb.append("(" + top.val);

                // 这里必须先进行右子树判断若不为空，将右孩子先压入栈。（保证左孩子先被窥探与弹栈）
                if (top.right != null) {
                    stack.push(top.right);
                }

                if (top.left != null) {
                    stack.push(top.left);
                }

                if (top.left == null && top.right != null) {
                    sb.append("()");
                }
            } else { // 如果窥探出的栈顶元素包含在set集合中，立即弹栈补右闭括号
                stack.pop();
                sb.append(")");
            }
        }
        return sb.substring(1,sb.length() - 1); // 首尾括号无必要
    }

    public static void main(String[] args) {
        根据二叉树创建字符串 o = new 根据二叉树创建字符串();

        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);

        treeNode1.left = treeNode2;
        treeNode2.left = treeNode4;
        treeNode1.right = treeNode3;

        String s = o.method(treeNode1); // 1(2(4))(3)

        System.out.println(s);
    }


    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

}
